//
// Created by YANHAI on 2020/6/27.
//

#include <stdio.h>
#include <memory.h>

void print_array(int *arr, int size)
{
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void merge(int *arr, int start, int mid, int end)
{
    int left_len, right_len;
    left_len = mid - start + 1;
    right_len = end - mid;
    int left_array[left_len], right_array[right_len];
    memcpy(left_array, arr + start, sizeof(int) * left_len);
    memcpy(right_array, arr + mid + 1, sizeof(int) * right_len);

    int i = 0, j = 0, k = start;
    while (i < left_len && j < right_len) {
        arr[k++] = left_array[i] < right_array[j] ? left_array[i++] : right_array[j++];
    }

    while (i < left_len) {
        arr[k++] = left_array[i++];
    }
}

void merge_sort(int *arr, int start, int end)
{
    if (start < end) {
        print_array(arr, 11);
        int mid = (start + end) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

int main()
{
    int arr[11] = {-1, 2, 4, -12, 4, 0, 0, 12, 23, -4, 7000};
    print_array(arr, 11);
    merge_sort(arr, 0, 10);
    print_array(arr, 11);
    return 0;
}